This invention relates to the field of packet data communication networks. It is more particularly directed to packet data transmission systems that provide service to individual packets based on defined policy criteria.
This invention addresses the problem of efficiently supporting multiple services in packet networks. A key aspect of such support involves discriminating among different packets based on their contents and administratively defined policies. Most packet data networks, including the global Internet and various enterprise networks based on the Internet protocol (IP), have employed a xe2x80x9cnondiscriminatory best-effort service model.xe2x80x9d In this model, network offers a uniform service to all traffic, in the sense that devices treat all packets equally in terms of their access to resources. An alternate model, known as xe2x80x9cpolicy based service differentiation modelxe2x80x9d has several advantages. In this model, network offers many kinds and levels of service where different packets may get different treatment based on administratively defined policies.
This latter service model is motivated by several factors. Firstly, the number and variety of applications that generate packet traffic in networks is continuously increasing. Each of these applications has varying networking service requirements. Secondly, technologies and protocols that enable provision of many kinds of services having different levels of security and Quality of Service (QoS) are widely available. However, access to these services needs to be regulated because these services consume resources such as network bandwidth, memory and processing cycles in network devices. Thirdly, business objectives or organizational goals may be better served by discriminating between different kinds of traffic in the network rather than by treating all traffic in a uniform manner.
The importance of these motivating factors is illustrated by considering some common examples:
Traffic generated by an application such as voice over IP (VOIP) requires a low delay service while that generated by a file transfer application can tolerate longer delays.
When two network service providers, or an enterprise and a network service provider, enter into a bilateral Service Level Agreement (SLA), the agreement may dictate that the service provider guarantee performance levels (e.g., bandwidth, delay, packet loss, etc.) to certain classes of traffic under specific conditions. Obviously, enforcement of such an SLA calls for policy based differentiation among various packets in the network.
Traffic generated by a web commerce application includes packets that carry sensitive financial transaction information which need a high level of security while most other web traffic does not.
A firewall that protects a company network may have to filter incoming traffic and selectively drop certain packets based on security policies.
A Virtual Private Network (VPN) implemented on a shared public packet data network may incorporate security and QoS features for specific categories of traffic.
As an example of how traffic could differ in its importance, consider the traffic generated by casual World-Wide-Web browsing by employees as opposed to that generated by important mission-critical applications. Since both kinds of traffic compete for the same network resources, the latter, being more important, should be insulated from the former.
A central requirement in enabling policy based service differentiation in packet networks, is that many network devices need to play an active role in classifying packets into categories based on applicable policy rules. It would be advantageous to have an efficient method to do such classification.
In general, rules that specify service differentiation policies are called Policy Rules and are of the form:
if (policy condition) then (policy action).
In the context of IP networks, which is one of the most common packet switched networks today, policy conditions are primarily specified in terms of various packet attributes. These attributes include header fields that identify source and destination addresses of the packet, applications identified by the source and destination port numbers, value of the protocol field, type-of-service-byte, etc. Additionally, policy conditions may also include other criteria such as time of day, identity of the local interfaces on which packet has arrived or will depart, etc. Such packet attributes and criteria used in choosing policy rules are herein referred to as xe2x80x98selectorxe2x80x99 attributes. In general, policy rules are range based in the sense that policy conditions of the policy rules are defined in terms of ranges of selector attribute values.
Policy actions in policy rules include accepting or dropping data packets (for instance, in the context of a firewall functionality), accepting or denying a request for resource reservation (for instance, in the context of a protocol such as RSVP), encrypting data packets, authenticating the sender, (for instance, in the context of the IPSEC standards), metering the data traffic, marking the type-of-service byte in packet header, shaping the traffic rate, (for instance, in the context of the differentiated services standards).
FIG. 1 is an example of how policy administration may be organized. It shows a scenario in which a set of rules are defined as security policy rules (e.g. drop all incoming traffic that is destined to port number X, encrypt all outgoing traffic originating from sources in the address range A1 . . . A2, and leaving on interface Y) and another set as policy rules for quality of service based discrimination (e.g. mark all traffic from sources in the address range A1 . . . A2 and leaving on interface Y as high priority). These sets of rules are installed in a device 100 through configuration from a configuration utility 110. Device 100 is a network edge device that provides service differentiation. It contains security enforcement (filtering) module 120 and quality of service enforcement (filtering) module 130. These modules are respectively responsible for security and quality of service based differentiations. During configuration, an administrator configures the two modules over an interface 115 providing the modules 120130 with their corresponding policy rules. Such configuration is done from a console attached to the device. As data packets 140 arrive at device 100, the two modules 120 and 130 separately process the packet in an order that is determined by the device architecture. The data packets 145 leave the device after receiving appropriate conditioning treatment.
In this illustration, parts of the packet processing steps are similar in both modules 120 and 130. These steps involve determining which of the specified set of policy rules are applicable. Module 120 scans only the security policy rules, and module 130 scans only the quality of service policy rules. Each module also directly applies the relevant actions to packets once an applicable policy rule is found. Often, in practice, creating a meaningful higher level service requires combination of multiple lower level services. For example, a virtual private network service offering may combine both security and quality-of-service elements. In such a scenario, packets belonging to a certain class will require both security and quality of service specific actions. In the case illustrated in FIG. 1, this implies that such packets go through identical classification steps twice, once in module 120 and again in module 130. In general, in a network device architecture that implements policies through separate configuration of multiple service specific modules, there is likelihood of redundant steps in processing individual packets. This reduces the overall throughput.
The classification process to determine applicability of a set of policy rules to a packet is in itself a time consuming process. This is primarily because of the multiple dimensions and criteria involved. Each policy condition may be specified in terms of sub-nets or arbitrary address ranges (particularly when addresses are dynamically assigned) for source or destination, similarly for protocol and port number fields in IP packet headers. Assets are inefficiently used to preprocess a given set of rules and order them by priority. During packet processing, a module sequentially scans the list of policy rules to determine whether a given rule is applicable to the packet being processed. This is continued until a first match is found or the end of list is reached. If a match is found, the module applies the actions specified in the matched rule and hands over the packet to the next module after completing its processing. If no match is found, packet receives the default treatment in the module. Since such a sequential search is time consuming, some of the recent published work has sought to design more efficient packet classification methods. Two of the most relevant ones are discussed below.
Given the increasing importance of policy based service differentiation in packet networks, there is a need for efficient solution to the multi-attribute packet classification problem. Since such classification often consumes computational resources affecting the device performance, it is advantageous that this be done using a few simple instructions and avoiding redundant processing.
The following are definitions of terms used herein:
Selector attribute: A packet""s attributes and/or administrative criteria used in defining policy conditions in policy rules. Values of selector attributes for a packet are used to determine which policy rules are applicable for that packet.
Policy Rule: A rule which specifies the specific treatment that is to be accorded to a particular class of packet traffic under defined conditions. It is generally of the form:
if (policy condition) then (policy action)
Policy Condition: A part of a policy rule that specifies a class of packet traffic and administrative criteria for which the rule applies. A policy condition is formally defined in terms of selector attributes.
Policy Action: A part of a policy rule that specifies particular action(s) to be executed when the policy rule is deemed applicable.
Range Based Policy Rule: A policy rule whose conditions can contain at least one range of values for one or more selector attributes.
Policy Based Classification: The process of determining which policy rules are applicable for a particular packet.
Multidimensional space: An Euclidean space in two or more dimensions. In an embodiment of the present invention, each dimension corresponds to a particular selector attribute.
Hypercube: Analogous to a rectangle in two dimensions or a cube in three dimensions. Also referred to herein as a box.
Point Location Problem: The problem of determining in which of a given set of hypercubes a given point in multidimensional space belongs. As used herein, the point location problem is obtained by modeling a packet to be classified based on policy rules as a point, and the policy rule conditions as hypercubes in a multidimensional space.
Hyperplane: Analogous to a line in two dimensions. In an advantageous embodiment of the present invention, a hyperplane is orthogonal to one of the coordinate axes.
Bounding Box: A hypercube that restricts the point location problem by guaranteeing that the given point must lie in this hypercube.
Left-subproblem: A smaller point location problem obtained by focusing on a portion of the multidimensional space that lies to the left (or any one side) of a chosen hyperplane.
Right-subproblem: A smaller point location problem obtained by focusing on the portion of the multidimensional space that lies to the right (or another side) of a chosen hyperplane.
Combined Policy-matching (or Policy rule matching) Engine (CPE): A module in the example architecture responsible for policy based packet classification.
Policy Manager/Repository (PMR): A module in the example architecture that stores the policy rules.
Policy Enforcement Entity (PEE): A module in the example architecture where actions specified by policy rules are executed.
Search Tree: A data structure that guides a policy classification process by specifying appropriate comparisons of selector attributes and branch instructions based on the results of a comparison.
Root Node: The first node of a search tree, where a packet classification process begins.
Intermediate Node: A non-terminal node of the search tree.
Leaf Node: A terminal node of the search tree.
Therefore, it is an aspect of the present invention to present methods, system, apparatus, computer devices and architecture for enabling policy based service differentiation in packet networks that reduce the number of packet classification steps.
It is yet another aspect of the present invention to provide a method of preprocessing a given set of policy rules by modeling the policy conditions in the policy rules as multidimensional boxes (hyper-cubes) to generate a search tree.
It is a further aspect of the present invention to provide a method of classifying packets to determine applicable policies with the help of the search tree using few and simple instructions.
It is still yet another aspect of the present invention to implement preprocessing of policy rules to build a search tree, and use the search tree to classify packets as computer readable program code contained on a computer usable medium.
In an embodiment of the present invention, the aforementioned aspects are achieved by identifying applicable actions for a packet in one classification step. This step itself uses few simple compare and branch instructions according to a search tree constructed by preprocessing policy rules using multidimensional box (hyper-cube) representations of policy rule conditions.